package com.ruijixiang.leetcode.everyday.leetcode2024.leetcode202408;

public class leetcode20240823 {
    public int[] findProductsOfElements(long[][] queries){
        int[] ans=new int[queries.length];
        for(int i=0;i<queries.length;i++){
            long[] q=queries[i];
            long er=sumE(q[1]+1);
            long el=sumE(q[0]);
            ans[i]=pow(2,er-el,q[2]);
        }
        return ans;
    }

    private long sumE(long k){
        long res=0;
        long n=0;
        long cnt1=0;// 之前填的1的个数
        long sumI=0;// 之前填的1的幂次之和
        for(long i=63-Long.numberOfLeadingZeros(k+1);i>=0;i--){
            long c=(cnt1<<i)+(i<<i>>1);// 新增的幂次个数
            if(c<=k){
                k-=c;
                res+=(sumI<<i)+((i*(i-1)/2)<<i>>1);
                sumI+=i;
                cnt1++;
                n|=1L<<i;// 填1
            }
        }
        // 剩余的k个幂次，由n的低k个1补充
        while(k-->0){
            res+=Long.numberOfTrailingZeros(n);
            n &=n-1;// 去掉最低为的1(置为0)
        }
        return res;
    }

    private int pow(long x,long n,long mod){
        long res=1%mod;// 注意mod可能等于1
        for(;n>0;n/=2){
            if(n%2==1){
                res=res*x%mod;
            }
            x=x*x%mod;
        }
        return (int)res;
    }
}
